package 面试题35_复杂链表的复制;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 23:18 2021/3/15
 * @Description：
 */

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Solution {

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        copyNodes(head);
        copyRandom(head);

        return reconnectNodes(head);
    }

    // 第一步：复制节点
    void copyNodes(Node head) {
        Node pCurNode = head;

        while (pCurNode != null) {
            Node pClonedNode = new Node(pCurNode.val);
            pClonedNode.next = pCurNode.next;

            pCurNode.next = pClonedNode;

            pCurNode = pClonedNode.next;
        }
    }

    // 第二步：复制随机指针
    void copyRandom(Node head) {
        Node pCurNode = head;

        while (pCurNode != null) {

            Node pClonedNode = pCurNode.next;

            if (pCurNode.random != null) {
                pClonedNode.random = pCurNode.random.next;
            }

            pCurNode = pCurNode.next.next;
        }
    }

    // 第三步：拆分链表，得到最终结果
//    Node reconnectNodes(Node head) {
//        Node newHead = head.next;
//
//        Node pCurNode = head;
//
//        //  一个节点一个节点的挪，每个节点都设置为指向跨越一个节点之后的节点
//        while (pCurNode.next != null) {
//            Node tmpNode = pCurNode.next;
//
//            pCurNode.next = tmpNode.next;
//
//            pCurNode = tmpNode;
//        }
//
//        return newHead;
//    }

    Node reconnectNodes(Node head) {
        //  同时处理两个链表
        Node newHead = head.next;

        Node pCurNodeOrig = head;
        Node pCurNodeNew = newHead;

        while (pCurNodeOrig != null) {
            pCurNodeOrig.next = pCurNodeOrig.next.next;
            pCurNodeNew.next = pCurNodeNew.next == null ? null : pCurNodeNew.next.next;


            pCurNodeNew = pCurNodeNew.next;
            pCurNodeOrig = pCurNodeOrig.next;
        }

        return newHead;
    }
}
